# -*- coding: utf-8 -*-

"""剑指 Offer II 112. 最长递增路径
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

示例 1：
输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4 
解释：最长递增路径为 [1, 2, 6, 9]。

示例 2：
输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4 
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

示例 3：
输入：matrix = [[1]]
输出：1

提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 231 - 1"""

class Solution:
    """最长增长路径，应该从一个图的‘起点’出发，找到该图的最远‘终点’
    起点就是入度为0的顶点，终点就是出度为0的顶点。
    那么需要将这个矩阵扫描一次，构件图，遍历每个起点，针对每个起点，寻找最远的终点。
    
    在用深度优先算法遍历一个起点的所有到终点的路径的时候，逻辑没问题，但是运算出现超时。发现是蛇形增长矩阵。
    所以我们能不能给定一个起点和一个终点，利用动态规划来计算。这个模型能用动态规划，因为两个顶点间不存在正反两条边。
    max_distance(begin, end) = max([max_distance(next_vertex1, end), max_distance(next_vertex2, end)...])+1
    计算所有(begin, end) 的组合，去最大值。
    
    在利用(begin, end)两个条件做动态规划时，有时面临起点集合与终点集合笛卡尔积过多的情况，也导致超时。
    反过来一想，我们不需要考虑终点，直接计算从起点开始到任何一个终点，在图里的长路径就可以了，这样计算效率又要提高许多。"""
    def longestIncreasingPath(self, matrix: list) -> int:
        row, coll = len(matrix), len(matrix[0])

        # 矩阵中每个顶点的id索引
        matrix_id = []
        i = 0
        while i < row:
            matrix_id.append([None,]*coll)
            j = 0
            while j < coll:
                matrix_id[i][j] = str(i)+'x'+str(j)
                j += 1
            i += 1

        # 建图
        gragh = dict()
        i = 0
        while i < row:
            j = 0
            while j < coll:
                center_val = matrix[i][j]
                center_id = matrix_id[i][j]
                if (i-1 >= 0) and (matrix[i-1][j] > center_val):
                    up_id = matrix_id[i-1][j]
                    if center_id in gragh.keys():
                        gragh[center_id].add(up_id)
                    else:
                        gragh[center_id] = set([up_id,])
                if (i+1 < row) and (matrix[i+1][j] > center_val):
                    down_id = matrix_id[i+1][j]
                    if center_id in gragh.keys():
                        gragh[center_id].add(down_id)
                    else:
                        gragh[center_id] = set([down_id,])
                if (j-1 >= 0) and (matrix[i][j-1] > center_val):
                    left_id = matrix_id[i][j-1]
                    if center_id in gragh.keys():
                        gragh[center_id].add(left_id)
                    else:
                        gragh[center_id] = set([left_id,])
                if (j+1 < coll) and (matrix[i][j+1] > center_val):
                    right_id = matrix_id[i][j+1]
                    if center_id in gragh.keys():
                        gragh[center_id].add(right_id)
                    else:
                        gragh[center_id] = set([right_id,])
                j += 1
            i += 1

        # print(gragh)

        # 获取起点, 终点
        vertex = set()
        i = 0
        while i < row:
            j = 0
            while j < coll:
                vertex.add(matrix_id[i][j])
                j += 1
            i += 1

        indegree_vertex = set()
        for indegree in gragh.values():
            indegree_vertex = indegree_vertex.union(indegree)
        begin_vertex = vertex - indegree_vertex

        outdegree_vertex = set(gragh.keys())
        end_vertex = vertex - outdegree_vertex

        # print('..............................')
        # print(begin_vertex)
        # print('------------------------------')
        # print(end_vertex)

        # # 计算最长路径（同时固定起点与终点）
        # cache = {}
        # def max_distance(b, e):
        #     if b not in gragh.keys():
        #         if b == e:
        #             return 1
        #         else:
        #             return float('-inf')

        #     k = (b, e)
        #     if k in cache:
        #         rs = cache[k]
        #     else:
        #         rs = max([max_distance(v, e) for v in gragh[b]]) + 1
        #         cache[k] = rs
        #     return rs

        # 计算最长路径（只是固定起点，到任意终点）
        cache = {}
        def max_distance(b):
            if b not in gragh.keys():
                return 1

            if b in cache:
                rs = cache[b]
            else:
                rs = max([max_distance(v) for v in gragh[b]]) + 1
                cache[b] = rs
            return rs

        max_step = 1
        for b in begin_vertex:
            # for e in end_vertex:
            max_step = max(max_distance(b), max_step)

        return max_step


if __name__ == '__main__':
    print(Solution().longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]))
    print(Solution().longestIncreasingPath([[3,4,5],[3,2,6],[2,2,1]]))
    print(Solution().longestIncreasingPath([[1]]))
    print(Solution().longestIncreasingPath([[0,1,2,3,4,5,6,7,8,9],[19,18,17,16,15,14,13,12,11,10],[20,21,22,23,24,25,26,27,28,29],[39,38,37,36,35,34,33,32,31,30],[40,41,42,43,44,45,46,47,48,49],[59,58,57,56,55,54,53,52,51,50],[60,61,62,63,64,65,66,67,68,69],[79,78,77,76,75,74,73,72,71,70],[80,81,82,83,84,85,86,87,88,89],[99,98,97,96,95,94,93,92,91,90],[100,101,102,103,104,105,106,107,108,109],[119,118,117,116,115,114,113,112,111,110],[120,121,122,123,124,125,126,127,128,129],[139,138,137,136,135,134,133,132,131,130],[0,0,0,0,0,0,0,0,0,0]]))
    print(Solution().longestIncreasingPath([[13,12,6,17,5,8,14,12,2,17,16,11,8,3,9,8,5,16,13,16,6,6,9,10,5,18,12,13,6,15,14,19,9,14,1,9,7,0,5,14,1,17,5,9,9,12,8,3,1,15,3,17,7,19,4,6,15],[1,3,5,15,8,13,19,12,19,6,16,15,18,5,5,7,5,12,17,15,1,10,8,9,8,12,6,12,4,7,17,11,12,15,19,18,6,6,2,18,17,9,13,19,11,8,4,5,19,2,9,5,6,3,15,5,15],[17,12,7,13,18,14,12,1,8,14,16,10,1,17,14,14,18,4,17,6,2,16,11,17,3,12,3,6,7,11,10,12,15,10,14,15,10,6,15,5,14,6,7,3,12,16,17,15,16,14,19,3,5,5,16,0,14],[10,13,1,7,17,4,2,3,7,11,5,14,8,3,0,4,7,5,13,13,2,2,16,5,1,15,15,3,18,0,8,5,11,3,3,18,17,14,19,16,10,13,16,15,2,9,18,12,17,0,17,11,4,6,5,15,19],[19,14,19,12,0,13,6,19,1,17,0,18,0,13,1,4,11,15,4,1,12,3,8,12,2,18,7,2,0,2,2,19,14,6,1,11,8,15,14,7,7,7,6,1,7,13,1,6,7,10,13,16,5,19,13,9,17],[1,7,19,13,6,16,1,15,1,6,18,3,18,1,5,5,16,19,2,3,4,9,9,0,18,2,5,19,2,10,15,15,9,5,0,9,15,16,9,8,19,9,11,14,18,6,3,7,8,7,8,19,12,5,11,9,18],[11,1,7,16,17,1,14,7,12,5,18,8,5,19,16,3,2,7,0,18,14,8,13,12,18,4,4,6,0,18,8,7,1,4,16,4,12,1,12,14,9,17,15,0,16,3,3,1,18,5,17,12,13,8,3,15,5],[18,13,2,0,1,4,12,19,9,7,12,4,11,12,18,19,9,14,0,12,2,8,6,3,19,7,2,11,7,18,17,19,9,15,15,11,4,9,14,18,13,12,6,4,1,5,19,2,13,19,9,11,3,1,13,15,9],[19,14,8,18,4,11,4,10,9,19,6,0,3,15,8,3,6,4,2,12,9,11,14,8,11,9,15,18,13,19,6,9,0,10,15,15,6,4,13,5,0,13,0,19,2,6,19,16,13,4,12,5,11,7,0,7,6],[5,17,3,4,19,10,1,16,19,5,4,0,1,16,5,19,0,15,19,17,0,19,16,15,15,15,15,7,1,15,2,11,17,1,14,18,17,1,17,7,1,14,0,19,1,16,19,11,2,17,7,18,19,6,10,1,5],[19,10,17,12,19,0,11,17,3,15,7,2,14,10,2,8,18,11,13,17,2,7,7,5,3,14,0,3,18,12,5,6,8,2,17,5,17,18,5,5,6,3,7,5,6,4,0,0,0,9,3,4,4,16,4,18,17],[3,7,11,14,3,11,10,13,7,14,15,11,19,5,16,4,4,14,15,19,11,18,17,14,14,6,14,8,19,14,1,7,11,3,15,14,18,6,9,19,5,10,15,15,9,17,8,7,12,16,3,3,10,12,11,14,11],[0,8,1,19,15,18,12,3,17,12,7,7,7,10,10,17,0,16,9,13,18,19,7,6,9,9,6,10,9,5,17,19,15,13,4,18,18,17,17,4,19,5,16,19,9,3,6,18,12,6,15,14,11,3,2,10,5],[18,14,3,9,13,18,13,17,9,11,5,13,6,6,1,18,18,9,17,13,14,2,16,18,10,3,18,2,14,14,5,16,17,5,12,17,13,15,19,16,9,1,15,13,5,11,17,14,12,7,18,10,1,16,19,2,19],[8,10,7,5,4,17,15,7,14,2,13,19,18,16,2,13,18,18,13,6,11,14,19,11,16,10,17,10,10,15,0,13,7,2,7,13,12,8,16,15,2,16,4,5,12,17,13,3,11,11,13,16,0,8,1,17,15],[8,10,14,5,16,9,1,11,5,17,8,10,0,4,13,11,12,19,4,9,12,0,10,7,1,3,13,8,9,5,9,13,9,15,1,8,3,3,11,16,15,14,15,2,15,11,10,15,19,5,0,8,15,18,19,2,10],[0,19,0,10,5,0,15,17,19,7,13,6,7,9,2,6,6,13,3,16,18,1,18,0,6,17,7,4,5,8,12,11,14,16,15,16,6,0,18,19,16,0,14,15,5,10,18,8,16,4,2,8,7,7,2,13,16],[11,0,5,4,0,2,11,1,18,3,10,9,0,6,0,2,0,0,1,13,7,3,2,4,3,3,9,19,19,13,15,17,2,0,1,10,16,3,0,0,2,2,4,12,9,17,16,14,7,3,12,0,18,5,3,19,1],[5,5,11,6,2,1,5,9,18,17,1,15,7,7,0,4,17,2,16,14,17,6,8,16,18,13,0,7,0,16,5,16,14,2,1,14,6,4,9,6,0,19,16,6,11,7,13,16,4,8,14,16,13,11,7,13,15],[6,6,12,1,9,1,10,12,2,7,18,19,4,0,19,12,0,19,8,18,5,14,2,14,11,8,6,1,3,4,12,0,9,15,4,3,6,15,1,8,4,19,19,19,13,15,10,19,13,10,2,12,5,11,9,17,9],[8,0,2,13,14,15,6,12,13,8,18,6,5,11,9,4,3,3,5,10,13,17,9,17,13,10,9,18,1,7,19,0,12,19,19,6,6,12,4,9,13,10,7,9,16,5,1,19,17,14,14,16,3,13,17,0,16],[3,2,17,7,19,13,11,10,18,8,17,11,12,16,3,8,2,1,17,11,15,14,19,19,15,5,2,17,6,1,2,15,6,18,18,14,16,10,6,1,14,9,12,10,19,4,11,4,15,4,0,3,1,13,10,0,2],[2,1,14,16,15,7,2,13,13,12,6,15,0,13,8,14,3,9,6,9,5,3,19,17,4,6,15,15,6,15,3,16,17,17,10,15,0,16,17,12,12,16,6,13,5,13,5,10,5,16,12,10,15,9,11,8,10],[13,9,4,17,6,6,0,7,1,11,7,19,12,12,10,6,2,7,12,18,0,15,15,7,14,15,10,2,3,6,1,17,15,5,14,17,3,4,3,11,14,18,0,2,18,19,3,7,5,0,9,7,12,9,12,18,7],[4,12,1,3,7,8,9,0,12,12,19,6,8,7,9,8,17,10,19,12,14,15,15,10,9,0,19,12,9,10,9,11,3,2,17,0,5,8,18,10,17,17,19,11,0,3,9,14,4,12,19,17,5,8,15,17,0],[5,16,16,2,4,4,5,6,7,10,14,18,9,1,7,9,14,17,11,19,17,12,13,2,12,18,6,12,3,10,5,10,12,16,4,0,15,3,6,12,6,8,14,13,12,13,15,12,16,17,17,13,5,9,17,0,8],[12,1,8,10,16,7,10,4,0,8,11,17,3,9,7,0,14,14,9,12,11,12,9,5,14,5,18,3,8,1,1,5,0,8,15,12,2,15,1,15,16,1,10,17,7,11,16,18,9,8,12,1,9,7,12,14,9],[15,10,16,18,2,6,7,19,5,2,18,18,4,18,4,19,9,3,8,11,12,6,18,6,7,5,4,5,15,2,11,18,7,16,0,10,8,6,19,5,14,13,7,11,19,15,2,2,18,13,0,7,12,17,17,10,18],[8,5,15,10,11,16,5,9,10,9,0,14,14,7,18,14,13,3,14,4,16,14,17,19,16,9,0,10,6,19,8,4,13,6,13,1,14,9,9,14,7,2,8,5,14,15,5,13,0,3,9,2,10,13,4,4,8],[14,5,10,1,11,18,2,4,13,9,0,12,13,19,12,11,12,7,17,13,5,8,16,4,7,2,2,0,13,7,1,1,11,7,14,13,11,2,1,9,14,6,14,12,18,3,5,15,1,8,1,19,0,9,17,11,13],[8,11,3,19,5,3,11,17,12,0,15,6,6,2,7,16,0,0,11,18,1,4,1,13,0,14,17,0,13,14,2,12,4,14,15,3,3,0,7,7,10,17,18,19,10,8,4,7,4,17,12,3,9,17,10,18,1],[11,11,8,3,6,6,1,8,19,19,1,5,14,15,14,12,4,3,12,8,2,12,16,1,3,8,15,2,1,6,11,13,14,8,9,1,9,6,14,19,2,3,0,11,8,8,12,3,14,17,3,2,14,9,18,11,15],[6,19,17,6,1,13,3,0,8,8,1,19,9,6,17,6,1,14,13,6,6,16,10,11,13,10,13,8,4,10,14,0,15,15,6,18,15,14,11,8,0,15,0,12,13,18,19,12,14,6,14,8,17,19,17,2,3],[11,17,10,1,15,15,8,2,0,13,11,1,14,10,4,4,19,18,16,8,1,4,11,8,19,11,10,18,12,16,0,10,11,14,5,12,17,9,16,8,7,1,3,17,0,15,17,7,16,6,12,12,0,16,8,11,7],[8,9,11,0,8,9,2,6,7,14,1,9,17,3,5,19,19,1,0,16,10,6,6,14,1,11,12,2,19,11,10,12,16,12,1,9,12,12,4,8,5,4,16,10,5,14,0,15,7,2,3,15,16,17,12,17,16],[5,7,7,18,16,6,7,5,14,1,2,16,6,16,9,16,15,14,4,19,9,9,15,13,4,12,4,4,3,6,9,12,18,15,4,4,10,6,0,1,13,5,16,16,7,13,0,12,19,9,4,6,0,9,10,5,9],[4,7,18,11,19,18,4,14,7,4,1,17,19,15,17,8,14,18,1,6,15,19,5,0,2,6,3,18,0,2,6,7,16,13,10,7,0,19,3,9,11,16,6,15,8,4,13,12,1,17,10,12,19,9,18,19,17],[13,8,15,17,9,17,4,14,13,13,4,13,10,12,16,15,11,2,10,18,15,12,19,4,0,19,5,17,1,8,6,3,17,7,17,9,4,6,19,8,4,6,1,17,13,8,5,2,1,9,15,17,4,12,11,9,7],[5,4,4,8,19,11,6,7,8,2,15,4,5,16,8,1,13,19,12,5,11,6,14,11,3,9,0,6,3,15,10,3,15,10,1,7,7,5,8,10,5,7,8,3,10,4,0,0,19,14,15,3,16,6,6,0,13],[17,7,15,2,18,13,3,9,18,7,4,11,16,7,6,0,19,7,2,12,13,6,10,14,14,13,1,5,17,18,5,10,11,11,18,4,18,1,12,3,14,3,4,0,4,17,8,4,3,13,13,8,9,16,11,16,14],[3,16,8,12,10,5,18,6,0,18,11,19,13,17,10,12,12,15,7,6,8,19,6,11,1,4,14,15,1,17,5,6,5,4,18,5,6,0,18,15,5,0,5,3,19,2,5,16,3,13,17,0,14,4,0,6,4],[18,1,19,0,3,11,4,6,16,2,10,2,19,1,2,14,4,15,16,10,16,12,19,7,5,1,4,13,2,16,17,5,1,19,1,15,18,16,10,19,18,2,10,15,18,3,18,1,14,17,8,1,15,8,17,13,1],[9,1,15,1,1,8,9,11,10,13,5,4,8,4,7,5,4,0,19,7,12,4,11,2,6,9,6,17,4,10,9,16,14,19,6,18,16,2,8,10,19,7,10,8,13,8,11,16,13,11,3,8,17,16,18,16,4],[14,4,4,4,1,18,9,12,10,4,0,8,12,8,16,14,12,17,7,13,0,14,5,5,0,19,9,1,5,18,4,5,19,19,8,8,7,16,18,19,6,12,4,17,18,12,3,10,19,0,12,7,12,13,18,15,12],[7,5,12,8,14,18,14,5,19,4,17,3,16,5,19,0,18,9,3,15,2,13,17,16,6,8,3,6,3,12,13,4,8,8,3,13,15,13,11,6,7,4,18,2,2,7,3,2,5,12,15,12,3,19,1,19,3],[14,14,16,1,16,1,6,4,15,16,19,9,11,7,8,17,4,7,16,13,12,8,6,3,16,12,8,14,9,7,8,3,18,19,14,14,0,8,0,0,9,14,19,6,10,7,9,8,2,17,1,5,12,2,7,7,1],[10,13,19,3,2,15,10,13,14,6,11,5,14,1,4,18,14,4,13,4,7,11,16,15,14,0,15,7,16,5,1,4,2,9,19,0,4,1,12,14,11,18,3,7,2,6,1,19,14,16,8,11,3,10,9,17,5],[14,15,13,16,5,13,4,14,8,6,2,15,12,17,18,11,14,7,5,14,17,17,8,8,17,3,8,11,16,7,19,7,10,8,10,8,9,11,17,4,11,11,4,12,14,13,16,17,15,7,5,12,11,14,11,11,3],[7,19,6,14,10,10,14,1,19,10,5,19,7,12,4,14,19,13,11,6,16,0,17,17,14,18,4,9,6,14,12,15,4,16,9,5,11,1,17,7,11,8,19,1,9,12,4,5,13,11,19,12,6,7,0,0,0],[15,12,14,19,5,5,13,9,19,12,3,4,17,12,15,1,2,17,1,17,10,6,15,6,0,10,13,3,0,13,11,6,18,11,2,11,15,13,13,10,4,19,6,18,0,15,2,0,18,13,10,19,5,5,13,17,9],[18,11,8,16,4,15,12,1,16,1,8,4,0,10,16,3,10,5,13,9,15,0,1,17,1,8,7,6,14,6,3,6,12,8,11,14,13,8,13,1,0,3,8,5,7,17,7,3,8,13,9,14,7,4,16,7,17],[0,5,12,8,3,16,19,15,18,17,2,13,5,10,14,6,1,5,1,5,9,6,6,6,8,19,15,7,7,4,5,3,16,1,11,11,16,11,4,13,3,10,17,11,19,6,0,4,9,10,1,10,19,6,10,12,11],[9,12,0,17,1,13,18,18,7,12,7,17,16,17,4,2,7,2,15,9,14,3,16,9,18,4,6,15,10,4,10,7,4,2,5,17,16,19,13,9,3,10,5,9,16,14,5,8,18,2,14,12,5,7,19,0,11],[18,14,12,3,1,3,15,5,13,18,0,17,5,1,5,18,14,4,9,19,7,12,7,12,8,11,4,16,12,13,18,4,12,9,16,16,3,0,11,2,3,12,18,7,14,14,14,18,15,8,12,8,7,4,5,6,1],[6,5,6,14,2,15,9,5,7,12,10,19,1,11,16,14,13,14,14,6,3,16,12,1,17,19,19,12,3,12,6,15,3,14,4,4,9,3,17,2,5,3,12,9,14,11,16,2,15,1,15,0,1,4,1,1,12],[14,9,12,3,2,14,13,7,11,13,0,8,15,10,14,14,19,7,13,7,16,4,10,6,7,10,6,17,0,15,2,8,4,18,12,13,18,12,16,17,18,14,4,17,6,19,5,2,13,3,18,15,16,14,2,0,7],[18,6,16,10,15,1,17,2,13,17,9,12,14,19,9,17,19,1,4,15,16,4,13,0,19,2,11,13,4,3,15,2,8,1,9,1,10,1,0,16,15,5,2,5,18,11,15,1,15,16,11,16,17,14,16,13,11],[11,11,18,16,8,14,16,11,19,19,1,18,14,16,1,3,17,17,7,6,2,16,13,6,11,16,5,2,12,10,0,0,7,11,11,8,6,2,8,4,12,5,10,13,17,1,6,2,1,7,0,0,7,19,14,1,11],[13,8,11,1,3,16,2,16,18,0,18,8,1,11,14,8,12,0,17,1,3,7,11,8,9,3,14,7,13,12,8,12,3,6,16,13,0,18,0,16,9,2,9,6,13,0,6,11,4,0,0,15,7,11,3,12,2],[8,3,17,0,18,10,10,17,4,13,1,16,14,2,9,0,11,1,13,14,0,19,17,16,1,8,18,8,7,18,12,12,7,10,10,14,13,15,16,18,17,10,4,15,7,1,4,15,17,17,13,18,19,14,14,2,7],[15,7,2,11,6,7,17,12,17,17,18,13,1,4,1,5,11,11,13,14,17,5,18,19,11,12,3,9,19,1,4,18,12,0,1,10,2,15,19,11,15,2,1,1,1,9,11,8,13,13,11,19,1,16,4,17,6],[8,0,13,5,12,3,18,18,0,2,13,8,14,18,9,12,14,6,6,13,10,0,2,10,3,8,5,14,17,14,11,2,5,18,8,12,1,18,11,3,12,4,8,4,1,12,5,16,4,1,12,1,8,3,15,11,7],[0,5,19,19,4,17,18,18,11,9,13,2,3,18,10,18,8,2,11,17,7,15,7,12,10,14,0,0,10,16,8,0,12,6,9,8,10,8,16,7,9,13,4,13,16,5,15,14,8,16,17,8,16,3,8,3,18],[5,15,8,15,4,5,15,6,18,19,2,11,2,3,0,7,12,16,15,6,18,9,3,18,2,1,7,15,1,5,13,7,1,18,5,3,3,15,7,1,19,2,19,13,5,3,3,18,2,17,12,1,4,2,13,10,15],[12,14,16,9,9,13,16,1,7,3,6,9,12,1,10,13,18,5,10,0,4,17,5,14,17,16,9,3,17,9,6,4,9,16,10,0,4,19,14,14,5,14,19,18,6,11,3,13,2,17,10,7,18,4,8,13,13],[19,9,3,2,2,4,16,16,3,14,16,6,7,11,16,10,18,3,18,19,4,14,15,6,16,19,18,5,19,7,2,11,5,10,17,5,8,15,1,19,18,0,15,19,14,10,14,14,10,14,18,0,13,14,19,7,8],[15,10,13,19,3,6,19,17,16,11,14,0,19,17,3,12,0,4,16,8,11,13,10,12,8,12,10,5,0,0,16,18,12,5,10,3,15,13,4,9,19,11,9,6,9,4,19,15,18,15,11,8,15,8,10,18,13],[2,11,9,10,19,3,2,0,13,13,12,11,10,7,19,7,0,10,8,8,19,16,13,9,5,17,6,12,17,13,18,12,15,1,0,15,19,13,19,3,9,8,17,7,18,0,17,19,2,17,9,16,10,17,15,10,0]]))
